public class fecursion {
    //int n = 6;
    //int num = frog(n);
//        int num = fibonacci(n);
//        int num = aum(n);
//        System.out.println(num);
//        print(n);


    /**
     * 1: A → C     1                      2^1 - 1
     * 2: A → B   A → C  B → C     3       2^2 - 1
     * 3: A → C   A → B  C → B   A → C   B → A   B → C   A → C     7   2^3 - 1
     * 4:
     * 64:  2^64 - 1
     * ——————————————————————————————————————————————————————————————————————————
     * @param n  盘子的数目
     * @param a  起始位置
     * @param b  中途位置
     * @param c  结束位置
     */
    public static void hannuota(int n,char a,char b,char c){
        if(n == 1){
            move(a,c);
        }else{
            hannuota(n-1,a,c,b);  //这里传参需要根据方法对应位置，在这一步，通过C将n-1盘子移动到b，b在这一步是结束位置
            move(a,c);
            hannuota(n-1,b,a,c);
        }
    }
    public static void move(char pos1,char pos2){
        System.out.print(pos1 + "->" + pos2 + " ");
    }
    public static void main(String[] args) {
        hannuota(1,'A','B','C');
        System.out.println();
        hannuota(2,'A','B','C');
        System.out.println();
        hannuota(3,'A','B','C');
        System.out.println();
    }
    public static int aum(int n){
        if(n == 1){
            return 1;
        }
        return n * aum(n-1);
    }
    public static int add1(int n){
        if(n == 1){
            return 1;
        }
            return n + add1(n - 1);
    }
    public static void print(int n){
        if(n > 10){
            print(n / 10);
        }
        System.out.print(n % 10 + " ");
    }
    public static int add(int n){
        if(n < 10){
            return n;
        }else{
            return (n%10) + add(n /= 10);

        }
    }
    public static int fibonacci(int n){
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 1;
        }
        return fibonacci(n-1) + fibonacci(n-2);
    }
    public static int frog(int n){
        if(n == 1){
            return 1;
        }
        if(n == 2){
            return 2;
        }
        return frog(n-1) + frog(n-2);
    }
}
